1. Field of the Invention
This invention relates to techniques for maintaining the hard quality of service (QoS) of the developing Internet. In particular, it relates to a method and system for controlling the admissible ingress and egress traffic of edge routers of the Internet and for balancing loads among equal-distance shortest paths for achieving a non-blocking Internet.
2. Description of Related Art
Internet Protocol (IP) networks are traditionally designed to support a best-effort service, with no guarantees on the reliability and the timely delivery of the packets. In interconnected packet networks, such as the Internet, users establish a connection between a source and a destination with a stream of data packet transferred through the network over a network path. The network path is defined by a set of nodes interconnected by a set of links through which packets of the connection are transferred. The network path can be generated by a variety of algorithms, such as the Dijkstra's shortest path algorithm or the like. Packet networks may have a hierarchical structure in which smaller networks are interconnected by larger networks. A packet network connects to one or more other packet networks through ingress and egress points (routers) of the network.
Interior routing protocols are employed by network routers to determine a path through the internal routers of the network along which packets between the ingress and the egress routers are forwarded. Packets received by a router are forwarded to other routers of the network based on a forwarding table constructed in accordance with the interior routing protocol, but may also be forwarded through routes installed with explicit route provisioning. Interior routing protocols may also specify network topology, link capacity/usage, and link-state information (“network information”) that is exchanged between the network routers. Network information allows the routers to construct the corresponding forwarding table. Examples of widely used interior routing protocols, and most relevant to this invention, are the Open Shortest Path First (OSPF) and IS-IS protocols. Common routing protocols such as OSPF and IS-IS choose least-cost paths using link weights, so inferred weights provide a simple, concise, and useful model of intra-domain routing. In this model, every link is labeled with a number called the weight or cost; conventionally this link weight may be a function of delay time, average traffic, and sometimes simply the number of hops between nodes.
As IP networks mature and are increasingly being used to support real-time applications, such as voice onto IP-based platforms, the existing IP networks need to provide a new level of QoS for such new applications. Differentiated Services (DiffServ) have become the main QoS architecture for the Internet. DiffServ avoids per-flow bandwidth reservation inside the network. It classifies flows into aggregates (classes), and provides appropriate QoS for the aggregates. A small bit-pattern in each packet—the ToS octet of IPv4 or the Traffic Class octet of IPv6—is used to mark a packet for receiving a particular forwarding treatment at each network node. A service level agreement (SLA) is signed between a service provider and customers to specify the type of services and the amount of traffic required for each type. An SLA codifies what a provider promises to deliver in terms of what, how, and associated penalties for failures.
QoS requirements of the premium class of traffic need to be achieved with components in both the data-plane and the control-plane. Data-plane components include traffic shaping and policing, traffic classification, scheduling and buffer management. Control-plane components include signaling and flow admission control (FAC) and network provisioning/traffic engineering. Effective implementations of data-plane components are well understood and available; only local state information in a router or switch is required.
In contrast, control-plane components, such as FAC and network dimensioning, remain open issues. When link-state information or link-bandwidth information (e.g., connectivity or available bandwidth) is exchanged between routers, each router in the network has a complete description of the network's topology. The challenges of the control-plane design arise from the fact that the implementations of control-plane components need the state information of the entire network. Typically, there are millions of flows traversing through a high-speed link, and therefore maintaining the state information of all links of the entire network is simply not practical.
There are several proposals for FAC. The general concerns about these proposals include the following.
(a) Scalability and Effectiveness: referring to FIG. 1, the network equipment that performs provisioning, resource management and FAC is called bandwidth broker (BB). BB architecture implies that admission control decisions are made at a central location for each administrative domain, such as ISP A 101 and ISP B 105. Although the cost of handling service requests is significantly reduced, it is unlikely that this approach can be scaled upward for large networks. In order to cope with scalability, most relevant studies adopt distributed admission control schemes, which are further distinguished into model-based and measurement-based approaches. Both approaches assess QoS deterioration probability upon service request arrivals; model-based approaches maintain state information for active services and employ mathematical models, whereas measurement-based approaches rely on either passive or active aggregate measurements. The main concern is the effectiveness of the schemes. The centralized FAC, although not scalable, can provide better QoS than the distributed admission control schemes.
(b) Applicability to Inter-domain QoS: All FAC schemes must fully address the inter-domain QoS issues. It is anticipated that there will be significant variation in the implementations and resource management strategies from one ISP to another. It is unlikely that we will find a unified approach across the Internet. Cascading different QoS approaches will work only if they cooperate with each other, which is difficult to achieve. For example, if one network uses measurement-based FAC and the other uses model-based FAC, it is unlikely that the end-to-end QoS can be achieved as anticipated for a flow path passing through the two networks.
While some QoS capabilities in an isolated environment have been demonstrated, providing end-to-end QoS at a large scale and across domain boundaries remains a challenging and unsolved problem. A need exists for designing a new and practical FAC scheme to maintain the QoS in the future Internet.
In another patent application filed on Oct. 3, 2005 with Ser. No. 11/243,117, commonly assigned to the Hong Kong University of Science & Technology, we proposed the concept of non-blocking networks to solve the QoS problem and simplify the FAC design of an MPLS Internet backbone network. A network is called non-blocking if it can always accommodate a new flow (or a dynamic service-level-agreement) as long as the ingress and the egress nodes or routers have capacity to set up the flow. One major advantage of the invention is that, if a network is non-blocking, its FAC will be greatly simplified as we do not need to check the capacity utilization of all internal links. Those methods described in U.S. patent application Ser. No. 11/243,117 are for MPLS-type networks that use explicit routing. The Internet uses destination-based routing where each node uses the destination of the packet to route the packet. Destination-based routing is also called hop-by-hop routing. Therefore, there is a need for a method, apparatus, and system for designing a non-blocking hop-by-hop backbone network.